<!DOCTYPE HTML>
<html>
<head>
<meta charset="UTF-8">
<title>Optimal interconnect wire sizing</title>
<link rel="canonical" href="/Users/mcgrant/Projects/CVX/examples/circuit_design/html/wire_sizing.html">
<link rel="stylesheet" href="../../examples.css" type="text/css">
</head>
<body>
<div id="header">
<h1>Optimal interconnect wire sizing</h1>
Jump to:&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#source">Source code</a>&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#output">Text output</a>
&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#plots">Plots</a>
&nbsp;&nbsp;&nbsp;&nbsp;<a href="../../index.html">Library index</a>
</div>
<div id="content">
<a id="source"></a>
<pre class="codeinput">
<span class="comment">% Section 5.1, L. Vandenberghe, S. Boyd, and A. El Gamal</span>
<span class="comment">% "Optimizing dominant time constant in RC circuits"</span>
<span class="comment">% Original by Lieven Vandenberghe</span>
<span class="comment">% Adapted for CVX by Joelle Skaf - 11/25/05</span>
<span class="comment">% Modified by Michael Grant - 3/8/06</span>
<span class="comment">%</span>
<span class="comment">% we consider the problem of sizing an interconnect wire that connects</span>
<span class="comment">% a voltage source and conductance G to a capacitive load C. We divide the</span>
<span class="comment">% wire into n segments of length li, and width xi, i = 1,...,n, which is</span>
<span class="comment">% constrained as 0 &lt;= xi &lt;= Wmax. The total area of the interconnect wire</span>
<span class="comment">% is therefore sum(li*xi). We use a pi-model of each wire segment, with</span>
<span class="comment">% capacitors beta_i*xi and conductance alpha_i*xi.</span>
<span class="comment">% To minimize the total area subject to the width bound and a bound Tmax on</span>
<span class="comment">% dominant time constant, we solve the SDP</span>
<span class="comment">%               minimize        sum_{i=1}^20 xi*li</span>
<span class="comment">%                   s.t.        Tmax*G(x) - C(x) &gt;= 0</span>
<span class="comment">%                               0 &lt;= xi &lt;= Wmax</span>

<span class="comment">%</span>
<span class="comment">% Circuit parameters</span>
<span class="comment">%</span>

n=21;          <span class="comment">% number of nodes; n-1 is number of segments in the wire</span>
m=n-1;         <span class="comment">% number of segments</span>
beta = 0.5;    <span class="comment">% segment has two capacitances beta*xi</span>
alpha = 1;     <span class="comment">% conductance is alpha*xi per segment</span>
Go = 1;        <span class="comment">% driver conductance</span>
Co = 10;       <span class="comment">% load capacitance</span>
wmax = 1.0;    <span class="comment">% upper bound on x</span>

<span class="comment">%</span>
<span class="comment">% Construct the capacitance and conductance matrices</span>
<span class="comment">%   C(x) = C0 + x1 * C1 + x2 * C2 + ... + xn * Cn</span>
<span class="comment">%   G(x) = G0 + x1 * G1 + x2 * G2 + ... + xn * Gn</span>
<span class="comment">% We assemble the coefficient matrices together as follows:</span>
<span class="comment">%   CC = [ C0(:) C1(:) C2(:) ... Cn(:) ]</span>
<span class="comment">%   GG = [ G0(:) G1(:) G2(:) ... Gn(:) ]</span>
<span class="comment">%</span>

CC = zeros(n,n,m+1);
GG = zeros(n,n,m+1);
<span class="comment">% constant terms</span>
CC(n,n,1) = Co;
GG(1,1,1) = Go;
<span class="comment">% segment values</span>
<span class="keyword">for</span> i = 1 : n - 1,
    CC(i,  i,  i+1) = beta;
    CC(i+1,i+1,i+1) = beta;
    GG(i,  i,  i+1) = +alpha;
    GG(i+1,i,  i+1) = -alpha;
    GG(i,  i+1,i+1) = -alpha;
    GG(i+1,i+1,i+1) = +alpha;
<span class="keyword">end</span>
<span class="comment">% Reshape for easy Matlab use</span>
CC = reshape(CC,n*n,m+1);
GG = reshape(GG,n*n,m+1);

<span class="comment">%</span>
<span class="comment">% Compute points the tradeoff curve, and the four sample points</span>
<span class="comment">%</span>

npts    = 50;
delays  = linspace(400,2000,npts);
xdelays = [ 370, 400, 600, 1800 ];
xnpts   = length(xdelays);
areas   = zeros(1,npts);
xareas  = zeros(1,xnpts);
sizes   = zeros(m,xnpts);
<span class="keyword">for</span> i = 1 : npts + xnpts,

    <span class="keyword">if</span> i &gt; npts,
        xi = i - npts;
        delay = xdelays(xi);
        disp( sprintf( <span class="string">'Particular solution %d of %d (Tmax = %g)'</span>, xi, xnpts, delay ) );
    <span class="keyword">else</span>,
        delay = delays(i);
        disp( sprintf( <span class="string">'Point %d of %d on the tradeoff curve (Tmax = %g)'</span>, i, npts, delay ) );
    <span class="keyword">end</span>

    <span class="comment">%</span>
    <span class="comment">% Construct and solve the convex model</span>
    <span class="comment">%</span>

    cvx_begin <span class="string">sdp</span> <span class="string">quiet</span>
        variable <span class="string">x(m)</span>
        variable <span class="string">G(n,n)</span> <span class="string">symmetric</span>
        variable <span class="string">C(n,n)</span> <span class="string">symmetric</span>
        minimize( sum(x) )
        G == reshape( GG * [ 1 ; x ], n, n );
        C == reshape( CC * [ 1 ; x ], n, n );
        delay * G - C &gt;= 0;
        0 &lt;= x &lt;= wmax;
    cvx_end

    <span class="keyword">if</span> i &lt;= npts,
        areas(i) = cvx_optval;
    <span class="keyword">else</span>,
        xareas(xi) = cvx_optval;
        sizes(:,xi) = x;

        <span class="comment">%</span>
        <span class="comment">% Plot the step response</span>
        <span class="comment">%</span>

        figure(xi+2);
        A = -inv(C)*G;
        B = -A*ones(n,1);
        T = linspace(0,2000,1000);
        Y = simple_step(A,B,T(2),length(T));
        hold <span class="string">off</span>; plot(T,Y,<span class="string">'-'</span>);  hold <span class="string">on</span>;
        xlabel(<span class="string">'time'</span>);
        ylabel(<span class="string">'v'</span>);

        <span class="comment">% compute threshold delay, elmore delay, dominant time constant</span>
        tthres=T(min(find(Y(n,:)&gt;0.5)));
        GinvC=full(G\C);
        tdom=max(eig(GinvC));
        telm=max(sum(GinvC'));
        plot(tdom*[1;1], [0;1], <span class="string">'--'</span>, telm*[1;1], [0;1],<span class="string">'--'</span>, <span class="keyword">...</span>
             tthres*[1;1], [0;1], <span class="string">'--'</span>);
        text(tdom,0,<span class="string">'d'</span>);
        text(telm,0,<span class="string">'e'</span>);
        text(tthres,0,<span class="string">'t'</span>);
        title(sprintf(<span class="string">'Step responses at the 21 nodes for solution (%d), Tmax=%g'</span>, xi, delay ));

    <span class="keyword">end</span>

<span class="keyword">end</span>

<span class="comment">%</span>
<span class="comment">% Plot the tradeoff curve</span>
<span class="comment">%</span>

figure(1)
ind = isfinite(areas);
plot(areas(ind), delays(ind));
xlabel(<span class="string">'Area'</span>);
ylabel(<span class="string">'Tdom'</span>);
title(<span class="string">'Area-delay tradeoff curve'</span>);
hold <span class="string">on</span>
<span class="keyword">for</span> k = 1 : xnpts,
    text( xareas(k), xdelays(k), sprintf( <span class="string">'(%d)'</span>, k ) );
<span class="keyword">end</span>


<span class="comment">%</span>
<span class="comment">% Draw wires for the four solutions</span>
<span class="comment">%</span>

figure(2)
m2 = 2 * m;
x1 = reshape( [ 1 : m ; 1 : m ], 1, m2 );
x2 = x1( 1, end : -1 : 1 );
y  = [ - 0.5 * sizes(x1,:) ; + 0.5 * sizes(x2,:) ; - 0.5 * sizes(1,:)  ];
x1 = reshape( [ 0 : m - 1 ; 1 : m ], m2, 1 );
x2 = x1( end : -1 : 1, 1 );
x  = [ x1 ; x2 ; 0 ];
h = fill( x, y, ones(4*m+1,1)*[0.9,0.8,0.7,0.6] );
hold <span class="string">on</span>
h2 = plot( x, y, <span class="string">'-'</span> );
axis([ -0.1, m + 0.1, min(y(:))-0.25, max(y(:))+0.1 ]);
colormap(gray);
caxis([-1,1]);
title(<span class="string">'Solutions at points on the tradeoff curve'</span>);
legends = {};
<span class="keyword">for</span> k = 1 : xnpts,
    set( h(k), <span class="string">'EdgeColor'</span>, get( h2(k), <span class="string">'Color'</span> ) );
    legends{k} = sprintf( <span class="string">'Tmax=%g'</span>, xdelays(k) );
<span class="keyword">end</span>
legend(legends{:},4);
</pre>
<a id="output"></a>
<pre class="codeoutput">
Point 1 of 50 on the tradeoff curve (Tmax = 400)
Point 2 of 50 on the tradeoff curve (Tmax = 432.653)
Point 3 of 50 on the tradeoff curve (Tmax = 465.306)
Point 4 of 50 on the tradeoff curve (Tmax = 497.959)
Point 5 of 50 on the tradeoff curve (Tmax = 530.612)
Point 6 of 50 on the tradeoff curve (Tmax = 563.265)
Point 7 of 50 on the tradeoff curve (Tmax = 595.918)
Point 8 of 50 on the tradeoff curve (Tmax = 628.571)
Point 9 of 50 on the tradeoff curve (Tmax = 661.224)
Point 10 of 50 on the tradeoff curve (Tmax = 693.878)
Point 11 of 50 on the tradeoff curve (Tmax = 726.531)
Point 12 of 50 on the tradeoff curve (Tmax = 759.184)
Point 13 of 50 on the tradeoff curve (Tmax = 791.837)
Point 14 of 50 on the tradeoff curve (Tmax = 824.49)
Point 15 of 50 on the tradeoff curve (Tmax = 857.143)
Point 16 of 50 on the tradeoff curve (Tmax = 889.796)
Point 17 of 50 on the tradeoff curve (Tmax = 922.449)
Point 18 of 50 on the tradeoff curve (Tmax = 955.102)
Point 19 of 50 on the tradeoff curve (Tmax = 987.755)
Point 20 of 50 on the tradeoff curve (Tmax = 1020.41)
Point 21 of 50 on the tradeoff curve (Tmax = 1053.06)
Point 22 of 50 on the tradeoff curve (Tmax = 1085.71)
Point 23 of 50 on the tradeoff curve (Tmax = 1118.37)
Point 24 of 50 on the tradeoff curve (Tmax = 1151.02)
Point 25 of 50 on the tradeoff curve (Tmax = 1183.67)
Point 26 of 50 on the tradeoff curve (Tmax = 1216.33)
Point 27 of 50 on the tradeoff curve (Tmax = 1248.98)
Point 28 of 50 on the tradeoff curve (Tmax = 1281.63)
Point 29 of 50 on the tradeoff curve (Tmax = 1314.29)
Point 30 of 50 on the tradeoff curve (Tmax = 1346.94)
Point 31 of 50 on the tradeoff curve (Tmax = 1379.59)
Point 32 of 50 on the tradeoff curve (Tmax = 1412.24)
Point 33 of 50 on the tradeoff curve (Tmax = 1444.9)
Point 34 of 50 on the tradeoff curve (Tmax = 1477.55)
Point 35 of 50 on the tradeoff curve (Tmax = 1510.2)
Point 36 of 50 on the tradeoff curve (Tmax = 1542.86)
Point 37 of 50 on the tradeoff curve (Tmax = 1575.51)
Point 38 of 50 on the tradeoff curve (Tmax = 1608.16)
Point 39 of 50 on the tradeoff curve (Tmax = 1640.82)
Point 40 of 50 on the tradeoff curve (Tmax = 1673.47)
Point 41 of 50 on the tradeoff curve (Tmax = 1706.12)
Point 42 of 50 on the tradeoff curve (Tmax = 1738.78)
Point 43 of 50 on the tradeoff curve (Tmax = 1771.43)
Point 44 of 50 on the tradeoff curve (Tmax = 1804.08)
Point 45 of 50 on the tradeoff curve (Tmax = 1836.73)
Point 46 of 50 on the tradeoff curve (Tmax = 1869.39)
Point 47 of 50 on the tradeoff curve (Tmax = 1902.04)
Point 48 of 50 on the tradeoff curve (Tmax = 1934.69)
Point 49 of 50 on the tradeoff curve (Tmax = 1967.35)
Point 50 of 50 on the tradeoff curve (Tmax = 2000)
Particular solution 1 of 4 (Tmax = 370)
Particular solution 2 of 4 (Tmax = 400)
Particular solution 3 of 4 (Tmax = 600)
Particular solution 4 of 4 (Tmax = 1800)
</pre>
<a id="plots"></a>
<div id="plotoutput">
<img src="wire_sizing__01.png" alt=""> <img src="wire_sizing__02.png" alt=""> <img src="wire_sizing__03.png" alt=""> <img src="wire_sizing__04.png" alt=""> <img src="wire_sizing__05.png" alt=""> <img src="wire_sizing__06.png" alt=""> 
</div>
</div>
</body>
</html>